<HTML>
<!--
  -- Copyright (c) 1996-1999
  -- Silicon Graphics Computer Systems, Inc.
  --
  -- Permission to use, copy, modify, distribute and sell this software
  -- and its documentation for any purpose is hereby granted without fee,
  -- provided that the above copyright notice appears in all copies and
  -- that both that copyright notice and this permission notice appear
  -- in supporting documentation.  Silicon Graphics makes no
  -- representations about the suitability of this software for any
  -- purpose.  It is provided "as is" without express or implied warranty.
  --
  -- Copyright (c) 1994
  -- Hewlett-Packard Company
  --
  -- Permission to use, copy, modify, distribute and sell this software
  -- and its documentation for any purpose is hereby granted without fee,
  -- provided that the above copyright notice appears in all copies and
  -- that both that copyright notice and this permission notice appear
  -- in supporting documentation.  Hewlett-Packard Company makes no
  -- representations about the suitability of this software for any
  -- purpose.  It is provided "as is" without express or implied warranty.
  --
  -->
<Head>
<Title>search_n</Title>
<!-- Generated by htmldoc -->
</HEAD>
<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" 
	ALINK="#ff0000"> 
<IMG SRC="CorpID.gif" 
     ALT="SGI" HEIGHT="43" WIDTH="151"> 
<!--end header-->
<BR Clear>
<H1>search_n</H1>

<Table CellPadding=0 CellSpacing=0 width=100%>
<TR>
<TD Align=left><Img src = "algorithms.gif" Alt=""   WIDTH = "194"  HEIGHT = "38" ></TD>
<TD Align=right><Img src = "function.gif" Alt=""   WIDTH = "194"  HEIGHT = "38" ></TD>
</TR>
<TR>
<TD Align=left VAlign=top><b>Category</b>: algorithms</TD>
<TD Align=right VAlign=top><b>Component type</b>: function</TD>
</TR>
</Table>

<h3>Prototype</h3>
<tt>Search_n</tt> is an overloaded name; there are actually two <tt>search_n</tt>
functions.
<pre>
template &lt;class <A href="ForwardIterator.html">ForwardIterator</A>, class Integer, class T&gt;
ForwardIterator search_n(ForwardIterator first, ForwardIterator last,
                         Integer count, const T&amp; value);

template &lt;class <A href="ForwardIterator.html">ForwardIterator</A>, class Integer, 
          class T, class <A href="BinaryPredicate.html">BinaryPredicate</A>&gt;
ForwardIterator search_n(ForwardIterator first, ForwardIterator last,
                         Integer count, const T&amp; value,
                         BinaryPredicate binary_pred);
</pre>		   
<h3>Description</h3>
<tt>Search_n</tt> searches for a subsequence of <tt>count</tt> consecutive elements 
in the range <tt>[first, last)</tt>, all of which are equal to <tt>value</tt>. <A href="#1">[1]</A>
It returns an iterator pointing to the beginning of that subsequence,
or else <tt>last</tt> if no such subsequence exists.  The two versions of 
<tt>search_n</tt> differ in how they determine whether two elements are the same:
the first uses <tt>operator==</tt>, and the second uses the user-supplied
<A href="functors.html">function object</A> <tt>binary_pred</tt>.
<P>
The first version of <tt>search</tt> returns the first iterator <tt>i</tt> in the
range <tt>[first, last - count)</tt> <A href="#2">[2]</A> such that, for every iterator <tt>j</tt> in
the range <tt>[i, i + count)</tt>, <tt>*j == value</tt>.  The second version 
returns the first iterator <tt>i</tt> in the
range <tt>[first, last - count)</tt> such that, for every iterator <tt>j</tt> in
the range <tt>[i, i + count)</tt>, <tt>binary_pred(*j, value)</tt> is <tt>true</tt>.
<h3>Definition</h3>
Defined in the standard header <A href="algorithm">algorithm</A>, and in the nonstandard
backward-compatibility header <A href="algo.h">algo.h</A>.
<h3>Requirements on types</h3>
For the first version:
<UL>
<LI>
<tt>ForwardIterator</tt> is a model of <A href="ForwardIterator.html">Forward Iterator</A>.
<LI>
<tt>Integer</tt> is an integral type.
<LI>
<tt>T</tt> is a model of <A href="EqualityComparable.html">EqualityComparable</A>.
<LI>
<tt>ForwardIterator</tt>'s value type is a model of <A href="EqualityComparable.html">EqualityComparable</A>.
<LI>
Objects of <tt>ForwardIterator</tt>'s value type can be compared for
   equality with Objects of type <tt>T</tt>.
</UL>
For the first version:
<UL>
<LI>
<tt>ForwardIterator</tt> is a model of <A href="ForwardIterator.html">Forward Iterator</A>.
<LI>
<tt>Integer</tt> is an integral type.
<LI>
<tt>T</tt> is a model of <A href="EqualityComparable.html">EqualityComparable</A>.
<LI>
<tt>BinaryPredicate</tt> is a model of <A href="BinaryPredicate.html">Binary Predicate</A>.
<LI>
<tt>ForwardIterator</tt>'s value type is convertible to <tt>BinaryPredicate</tt>'s
   first argument type.
<LI>
<tt>T</tt> is convertible to <tt>BinaryPredicate</tt>'s second argument type.
</UL>
<h3>Preconditions</h3>
<UL>
<LI>
<tt>[first, last)</tt> is a valid range.
<LI>
<tt>count</tt> is non-negative <A href="#1">[1]</A>.
</UL>
<h3>Complexity</h3>
Linear.  <tt>Search_n</tt> performs at most <tt>last - first</tt> comparisons.
<P>
(The C++ standard permits the complexity to be <i>O</i>(<tt>n</tt> (<tt>last</tt> - <tt>first</tt>)),
but this is unnecessarily lax.  There is no reason for <tt>search_n</tt> to
examine any element more than once.)
<h3>Example</h3>
<pre>
bool eq_nosign(int x, int y) { return abs(x) == abs(y); }

void lookup(int* first, int* last, size_t count, int val) {
  cout &lt;&lt; &quot;Searching for a sequence of &quot;
       &lt;&lt; count
       &lt;&lt; &quot; '&quot; &lt;&lt; val &lt;&lt; &quot;'&quot;
       &lt;&lt; (count != 1 ? &quot;s: &quot; : &quot;:  &quot;);
  int* result = search_n(first, last, count, val);
  if (result == last)
    cout &lt;&lt; &quot;Not found&quot; &lt;&lt; endl;
  else
    cout &lt;&lt; &quot;Index = &quot; &lt;&lt; result - first &lt;&lt; endl;
}

void lookup_nosign(int* first, int* last, size_t count, int val) {
  cout &lt;&lt; &quot;Searching for a (sign-insensitive) sequence of &quot;
       &lt;&lt; count
       &lt;&lt; &quot; '&quot; &lt;&lt; val &lt;&lt; &quot;'&quot;
       &lt;&lt; (count != 1 ? &quot;s: &quot; : &quot;:  &quot;);
  int* result = search_n(first, last, count, val, eq_nosign);
  if (result == last)
    cout &lt;&lt; &quot;Not found&quot; &lt;&lt; endl;
  else
    cout &lt;&lt; &quot;Index = &quot; &lt;&lt; result - first &lt;&lt; endl;
}

int main() {
  const int N = 10;
  int A[N] = {1, 2, 1, 1, 3, -3, 1, 1, 1, 1};

  lookup(A, A+N, 1, 4);
  lookup(A, A+N, 0, 4);
  lookup(A, A+N, 1, 1);
  lookup(A, A+N, 2, 1);
  lookup(A, A+N, 3, 1);
  lookup(A, A+N, 4, 1);

  lookup(A, A+N, 1, 3);
  lookup(A, A+N, 2, 3);
  lookup_nosign(A, A+N, 1, 3);
  lookup_nosign(A, A+N, 2, 3);
}
</pre>
<P>
The output is
<pre>
Searching for a sequence of 1 '4':  Not found
Searching for a sequence of 0 '4's: Index = 0
Searching for a sequence of 1 '1':  Index = 0
Searching for a sequence of 2 '1's: Index = 2
Searching for a sequence of 3 '1's: Index = 6
Searching for a sequence of 4 '1's: Index = 6
Searching for a sequence of 1 '3':  Index = 4
Searching for a sequence of 2 '3's: Not found
Searching for a (sign-insensitive) sequence of 1 '3':  Index = 4
Searching for a (sign-insensitive) sequence of 2 '3's: Index = 4
</pre>
<h3>Notes</h3>
<P><A name="1">[1]</A>
Note that <tt>count</tt> is permitted to be zero: a subsequence of zero
elements is well defined.  If you call <tt>search_n</tt> with <tt>count</tt> equal
to zero, then the search will always succeed: no matter what <tt>value</tt>
is, every range contains a subrange of zero consecutive elements that
are equal to <tt>value</tt>.  When <tt>search_n</tt> is called with <tt>count</tt> equal to
zero, the return value is always <tt>first</tt>.
<P><A name="2">[2]</A>
The reason that this range is <tt>[first, last - count)</tt>, rather than
just <tt>[first, last)</tt>, is that we are looking for a subsequence whose
length is <tt>count</tt>; an iterator <tt>i</tt> can't be the beginning of such a
subsequence unless <tt>last - count</tt> is greater than or equal to <tt>count</tt>.
Note the implication of this: you may call <tt>search_n</tt> with arguments
such that <tt>last - first</tt> is less than <tt>count</tt>, but such a search will
always fail.
<h3>See also</h3>
<tt><A href="search.html">search</A></tt>, <tt><A href="find_end.html">find_end</A></tt>, <tt><A href="find.html">find</A></tt>, <tt><A href="find_if.html">find_if</A></tt>

<!--start footer--> 
<HR SIZE="6">
<A href="http://www.sgi.com/"><IMG SRC="surf.gif" HEIGHT="54" WIDTH="54" 
        ALT="[Silicon Surf]"></A>
<A HREF="index.html"><IMG SRC="stl_home.gif" 
        HEIGHT="54" WIDTH="54" ALT="[STL Home]"></A>
<BR>
<FONT SIZE="-2">
<A href="http://www.sgi.com/Misc/sgi_info.html" TARGET="_top">Copyright &copy; 
1999 Silicon Graphics, Inc.</A> All Rights Reserved.</FONT>
<FONT SIZE="-3"><a href="http://www.sgi.com/Misc/external.list.html" TARGET="_top">TrademarkInformation</A>
</FONT>
<P>
</BODY>
</HTML> 
